3D Coding TAT - Smooth Lines & Anti-Aliasing
The problem with 99% of the current wave of 3d game engines is the same one which Wolfenstein suffered from, blocky pixels. This pixellation occurs because small texture bitmaps are used to fill large screen polygons where the scale of each texel (textured pixel) is bigger than 1, so a texel is repeated any number of times to fill up a 4x4 or 8x8 or AxB subpolygon area. This scale-up problem or 'pixel zoom' is most visible when standing point-blank against a wall or 3d creature model. To combat this there are a few solutions, some good, some bad.
1. Use much large texture bitmaps (BAD) this chews up memory and the CPU cache is chewed to bits.
2. Use a scale for the projection/perspective calculation so that the item (polygon, line or pixel) is kept at a 1:1 zoom ratio. This means far bigger textures are needed (perhaps 640 or 768 lines high) to be able to fill a full screen polygon OR very big polygons are broken down into smaller ones. This means the maximum scale at the Z-clipping view plane is 1 pixel any more than this and pixel zoom occurs.
3. Large polygons use the mosiac or bathroom-tile technique to repeat the same small texture bitmap again and again to fill up the entire area.
4. Interpolation (either bi- or quad-) is used to average out the scaled up pixel blocks. Most 3d cards do this in hardware which is good news as the CPU normally has enough to do.
5. Some form of voxel-sprite hybrid method can be used. I believe that the Blade Runner game used this technique, although I haven't seen or played the game. It should give a far better way of creating smooth curves for organic (human) looking things and should give very good results for close range objects, but for small items in the distance this might be time consuming compared to normal texture mapping method.
6. Voxel based landscapes use smoothing techniques to help iron out the sharp corners between map cell corners.
1: Smooth & Fast Bresenham
After reading a short article by M. Abrash about this subject which described Xiaolin Wu 's anti-aliasing technique an idea came into my vacant head. I think it is possible to perform anti-aliasing with ONLY the Bresenham line drawing technique and nothing else simply by using the error term (which is actually the partial quotient formed by DIVIDING the major length by the minor length using repeated subtraction!). I haven't fully read about Wu's algorithm (which I believe uses a divide and has accumulative errors problems for very long lines) and I haven't explored this Bressy-only idea to any great length so more research is vital to discover or dispel this idea.
2: Recursive Terrain Mapping
This is a way to tackle the vast range in environment scaling in a sort-of-hierarchical way. To gain any reasonable level of realism for an exterior landscape you must be able to view it at a huge number of scales from a few inches away upto a number of miles away. The very distant and so very small landscape details are not really the problem (apart from the CPU having to skip bytes in the texture bitmap to scale it down), the real problem is the point-blank surfaces and objects which often resemble a blocky chess board rather than a highly detailed surface. To maintain a high level of quality detail down to a very small scale requires a high resolution description in the world data and that needs a huge polygon and vertex count. For example in an extreme case you may see a large metal water tank on the horizon and you may want to walk up close to it and see the individual rivets on the seams. In this case do you describe each and every rivet as a square polygon or do you simply use a pre-drawn metal bitmap with pixel size rivets on it? If you have played DOOM or Wolfenstein then you already know the blocky answer.
We want to be able to choose the amount of detail that we need to render depending on distance so we need a way to introduce high resolution detail or to reduce our workload for the mile away items on the horizon line. Okay, it seems sensible to start with a low-resolution (rough) stage and only increase the quality if and when we need to. This way we are not chugging through tons of unneeded data like when a very large bitmap is scaled down to fill a tiny polygon. The CPU really hates this skipping bytes, it much better prefers continuous bytes.
1. Rough stage (low detail, low resolution)
2. Medium stage (more detail, more resolution)
3. Fine stage (even more detail, high resolution)
So we start with the first stage and progress only if we need that extra detail, but how can we do this without sending the polygon & vertex count through the roof?
One of the most obvious solutions would be to employ fractals or some kind of sub-division method to zoom in on the 'detail' in real-time as the landscape or objects are being rendered. But there is one big problem, we would have no control over the fractals, the high detail created is just the some of a number of low detail parts. And in all honesty we have not created detail we have simply smoothed between some low resolution parts. So a green and brown texture used to draw a mile away, grass and mud hill when viewed from a few inches away would just be a fuzzy green and brown mess, we could NOT see individual blades of grass or stones in the muddy patches.
It seems that we need to go past the single pixel space of a bitmap and enter the sub-pixel dimension (spooky eh?).
Right enough waffle, here is my latest hair brain idea:
What about thinking of a bitmap texture as an array (not very ground breaking so far) but instead of thinking of each element as a single pixel we think of an element as being a thumbnail of another bitmap texture. Or to put it another way we have a rough (low detail) array of elements and each element is the token of another finer (higher detail) array.
i.e. "We have an array of array tokens."
Going back to the grass and mud example we would have a bitmap texture (the rough array) perhaps like this:
zoom-> gmgmgmgmgm g = 1 grass pixel
gggmmgmgmm m = 1 mud pixel
ggggmgmmmm
gggggggmgm
gggggggggg
Now suppose we zoom in on the top left corner, we have:
ggggmmmm -¿
ggggmmmm ³
ggggmmmm ³
gggggggg Ã-----------> gm...
gggggggg ³ gg...
gggggggg ³ .....
gggggggg --
BLOCKY (4x4 zoom) bitmap (1x1)
We know that each 'g' pixel represents a small area of grass and that 'm' is mud so why not use a 'blade of grass' bitmap for each 'g' pixel and a 'patch of mud' for each 'm' pixel?
This is the basic idea behind "Recursive Terrain Mapping". I have used to term 'pixel' where perhaps 'material' or 'token' or even 'atom' might have been more descriptive and correct. The good thing about this method is that large (high detail) array maps can be built up from other array maps just by using their token value as the elements in a rougher (lower detail) map array. And because it is an array of tokens we can reuse the same token any number of times, we could even use the token of the array itself (the recursive part of the title).
There are a couple of items which need to be resolved before this method becomes more practical.
1. Because one map is built from an (possibly) infinite number of sub-maps (i.e. itself) this might be rather slow.
2. A pixel is normally 1 byte in size so only 256 map tokens are possible.
3. The map array address must be calculated from the token.
In item 1 two maps could be used, one for the actual token array map and one for a pure pixel map. We only use the token map for large areas (close to the view-point) otherwise the pure pixel map is used as normal, this saves having to follow all the sub-maps possibly falling into an infinite loop. The current map or element scale determines which one is used. Also we would never really follow an infinite loop because we would stop at a minimum scale value (e.g. 1 pixel).
Item 2: This can be solved by using a word or a dword for each array element. This would also remove the need to convert a token to address the correct map 3.
This method is similar to real fractals (Julia & Mandel sets) and also fractal compression (IFS) where parts of an image (in this case a polygon texture) is built up from sub-images or parts of itself. But unlike real fractals this self-similarity is predefined within the array maps and using the tokens so can be controlled (designed by the graphics artist).
From a programming point of view this may appear slower than the standard one-polygon-per-face method with a little more added complexitity but remember that a really, really HUGE zoom is (perhaps) possible. Just imagine instead of a blocky mountain bitmap texture you could keep on magnifying it up to see rocks and beyond them to see tiny grains of sand. One thing to remember is that to reach this atomic scale you need to follow a number of intermediate levels first. The more you magnify, the more work is involved to follow the sibling bitmaps. This extra work isn't too bad when you consider that we are going to be filling a large area so the per-pixel workload probably isn't so great but the results hopefully are.
From a map designing and starting point of view I would suggest first creating the 'atomic' detail level (blades of grass, a brick for a wall, a slinter of wood) and then build larger maps of them (a clump of grass, a brick wall, a piece of wood) and then finally create the large region maps (a huge field of grass, a hill side, an entire building side and so on...). Now when you wish to design a new game world you can simply use a number of the big region maps to quickly slot together a highly detailed environment. You can think of this approach as being "tiles within tiles". One word of caution, don't be tempted into changing a 'small' detail as this would have a snowball effect on every large structure which has already used it.
The 'design' contribution comes from being able to build the maps from a number of finer detail map blocks, placing grass next to mud or mud next to water for example. Just as graphics artists can place individual pixels on a bitmap so too can they 'draw' with the atomic map components to create bigger and bigger items.
The only real downside on this technique is that surfaces are still planar, flat without bumps or dips.
3: Atomic Lumps & Bumps
We might be able to magnify a hill side texture to be able to see individual rocks or grains of sand but it is still flat, level with the rest of the hill. Everything would look like it had been run over by a steamroller. What we need to do is give them some depth, to make objects stand out from or receed into the background, to give the impression of viewing solid 3d items or atleast a 3d face. But by introducing depth into the hill for example we would need to define vertices or control points which could be used to shape the surface mesh.
We could introduce Z-depth data for each element in our recursive terrain map this way we control and design its shape as the map is magnified. The more the magnification increases, the more Z-depth information is needed. It is probably best to define 4 depth values (one for each corner) which are relative to our parent plane. With each successive sibling (sub-map) the magnitude of the Z-depth should be scaled down to relay its smaller scale. At the smallest, atomic scale the Z-depth could possibly always be 0.
But by injecting the Z-depth component some problems occur.
1. Projection/perspective calculations increase.
2. Clipping is more difficult (it's no longer co-planar).
3. Shading becomes more complicated, because the angle has changed.
Perhaps 'Bump Mapping' or a similar technique could be used to give the flat maps some appearance of roughness.
4: Stop Dithering ?
This can be one of the simplest ways to help disguise blocky ('pixellated') graphics where a single pixel has been used to fill a large area, usually where objects are very close to the player. Dithering normally means skipping every other pixel to give a 50% illusion of a image but it can give many more levels by altering the number and spacing between pixels (just like a newspaper picture).
You may think that this technique is too old and has been overtaken by proper shading using a look-up table to remap pixels to a predetermined (and precalculated) level or it has been made redundant through the use of interpolation or other smoothing techniques, but it can still be useful because of it's sheer speed. It allows mixing of two or more items without any real overhead in terms of extra calculation. I think that even UNREAL used 50% dithering on some of its old, preview screen shots at a screen resolution of 640x400. This method is probably only useful for software based rendering as modern 3-d hardware cards tend to have bi- or quad-linear interpolation to smooth out blocky pixels.
For normal 320x200 VGA resolutions this technique is not very good but for 640x400 the pixels are small enough that the viewer can not easily see the dithered pixels. At this resolution speed is the main problem and this dithering method can save 1000's and 1000's of instructions which would be needed for interpolation or smoothing across most of the screen. A rough estimation is that around 10 to 30% of pixels drawn on the screen would be blocky requiring smoothing, this at 640x400 would be 25600 to 76800 pixels.
Another use for the 50% dither could be to quickly draw shadows or to overlay scores and info over a background. It could also be used to extent the normal shading look-up method especially when you're restricted to just 256 colours. I've just played a demo of Monster Trucks 2 and I quickly noticed that the horizon-fade-in was not a fade-in, it used dithering. I have seen this technique used before on the Amiga for a racing game where trees and other objects were dithered (or 'screened'?) as they came into view. Because of the Amiga's bitplane method of storing the screens and the CPU's modest 8 Mhz clock, it was not possible to re-map (shade) each pixel as they are being drawn so a dithering method was used. Even a few Command & Conquer style games use 50% dithering around the edges of the explored game area where the player has yet to go. It's good to know that even the oldest techniques still have a place in today's super-cray-CPUs.